|
A geometric separator is a line (or other shape) that partitions a collection of geometric shapes into two subsets, such that proportion of shapes in each subset is bounded, and the number of shapes that do not belong to any subset (i.e. the shapes intersected by the separator itself) is small. When a geometric separator exists, it can be used for building divide-and-conquer algorithms for solving various problems in computational geometry. == Separators that are closed shapes == A simple case in which a separator is guaranteed to exist is the following: :: Given a set of ''n'' disjoint axis-parallel squares in the plane, there is a rectangle ''R'' such that, at most 2''n''/3 of the squares are inside ''R'', at most 2''n''/3 of the squares are outside ''R'', and at most O(sqrt(''n'')) of the squares are not inside and not outside ''R'' (i.e. intersect the boundary of ''R''). Thus, ''R'' is a geometric separator that separates the ''n'' squares into two subset ("inside ''R''" and "outside ''R''"), with a relatively small "loss" (the squares intersected by R are considered "lost" because they do not belong to any of the two subsets). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Geometric separator」の詳細全文を読む スポンサード リンク
|